# -*- coding: utf-8 -*- 
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2022/1/18
# @File : 215. 数组中的第K个最大元素.py
import random
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:

        def quicksort(l,r) -> int:

            pivot = random.randint(l,r)
            nums[pivot],nums[l] = nums[l],nums[pivot]

            i = l

            for j in range(l+1,r+1):
                if nums[j] < nums[l]:
                    i += 1
                    nums[i],nums[j] = nums[j],nums[i]
            nums[i],nums[l] = nums[l],nums[i]

            if i == target: return nums[i]
            elif i < target: return quicksort(i+1,r)
            else: return quicksort(l,i-1)

        target = len(nums) - k#如果问第k小就直接使用k-1
        return quicksort(0,len(nums)-1)
